题解 P2052 [NOI2011]道路修建

发表于 | 更新于

题意：给定一棵有$n$个节点的树，树上每条边花费的价格是这条边两侧的点的数量的差的绝对值与这条边长度的积。求这棵树的总花费。

随便选一个点作为根节点(这里选用节点$1$)，我们可以对这棵树进行$dfs$计算出每个点的$size$，然后就知道这条边的贡献为$abs(n-2\times size_{v})\times w_{i}$，其中$v$为这条边的儿子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
struct node{
    ll dis,to,next;
}e[3000000];
using namespace std;
inline void write(ll x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(ll x) {write(x);puts("");}
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
ll head[3000000],size[3000000],n,ans,cnt;
inline void add(ll u,ll v,ll d){
    e[++cnt].dis=d;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(ll u,ll fa){
    for (ll i=head[u];i;i=e[i].next){
        ll v=e[i].to;
        if (v==fa)continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}
void dfs1(ll u,ll fa){
    for (ll i=head[u];i;i=e[i].next){
        ll v=e[i].to;
        if (v==fa)continue;
        ans+=e[i].dis*abs(size[v]*2-n);
        dfs1(v,u);
    }
}
int main(){
    n=read();
    for (ll i=1;i<=n-1;++i){
        size[i]=1;
        ll u=read(),v=read(),d=read();
        add(u,v,d);add(v,u,d);
    }size[n]=1;
    dfs(1,0);
    dfs1(1,0);
    cout<<ans;
}